/*
 * @Author       : wangzeyu 2309335887@qq.com
 * @Date         : 2023-07-23 22:39:39
 * @LastEditors  : WangZeYu
 * @LastEditTime : 2023-07-23 23:11:14
 * @FilePath     : \my-study-js\algorithm\permutations.js
 * @Description  : 全排列leetcode46题
 *                 回溯算法：英文：Back Tracking 是 深度优先遍历+递归
 *                 全排列题目描述：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 */

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let permute = function (nums) {
  let result = []

  function backtrack(path) {
    if (nums.length == path.length) {
      result.push([...path])
      return
    }
    for (let i = 0; i < nums.length; i++) {
      if (path.indexOf(nums[i]) > -1) {
        continue
      }
      path.push(nums[i])
      backtrack(path)
      path.pop()
    }
  }

  backtrack([])

  return result
};

let nums = [1, 2, 3]
console.log(permute(nums));
